package Upr;

import java.util.Arrays;

public class quck {

	public static void main(String[] args)
	{
		int[] arr = {5,4,6,8,4,2,5,7,3,1,5,9,8,6,2,2,3,5,4,6,7,8,9,1};
		System.out.println(Arrays.toString(arr));
		
		quickSort(arr, 0, arr.length -1);
		System.out.println(Arrays.toString(arr));
		
	}

	static int partition ( int[] arr, int start, int end)
	{
		int pivot = arr[start];
		int storeInd = start + 1;
		for (int i = storeInd; i <= end; i++)
		{
			if(arr[i] < pivot)
			{
				swap(arr, i, storeInd);
				storeInd++;
			}
		}
		
		swap(arr, start, storeInd - 1);
		return storeInd - 1;
	}
	
	static void quickSort (int[] arr, int start, int end)
	{
		if(start > end)
		{
			return;
		}
		
		else 
		{
			int storeInd = partition(arr, start, end);
			quickSort(arr, start, storeInd - 1);
			quickSort(arr, storeInd + 1, end);
			
		}
		
		
	}

	private static void swap(int[] arr, int i, int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	
	
	
}
